#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        vector<int> temp;
        // 先排序简化问题
        sort(candidates.begin(), candidates.end());
        function<void(int, int)> func([&](int i, int sum) -> void
                                      {
            if(sum==target){
                res.push_back(temp);
                return;
            }
            if(sum>target||i>=candidates.size())
                return;
            if(candidates[i]+sum>target) return;
            //不选
            func(i+1,sum);
            //重复选
            temp.push_back(candidates[i]);
            func(i,sum+candidates[i]);
            temp.pop_back(); });
        func(0, 0);
        return res;
    }
};